easyexams

this blog is created to help all those who are preparing for compitative exams. I hope this blog helps you all in your preparation and to achieve your goal. ALL THE BEST

connect to the world around you

check more! XYZ!

vocab builder

IMPORTANT ARTICLES

How to Easily and Quickly Memorize Some Spellings that Many Students Get Wrong

Here are easy and quick tricks for remembering some spellings.

Once you go through these, you'll automatically remember most of them.

To permanently remember them, you can come back and revise once or twice more.

My best wishes for you.

principle, principal - A principle is a rule

Notice that both the words "principle" and the word "rule" have the letter "e".

The principal in a college is the main person there.

stationary, stationery - You write on stationery.

Or, stationery uses envelopes.

Notice the letter "e".

arithmetic - Use this sentence: A Rat In The House May Eat The Ice Cream.

The first letter of each word in this sentence makes the spelling ARITHMETIC.

believe - Believe

has a "lie" in it.

committee

- MM, TT, and EE met in a committee.

conscience

- Does science have a conscience.

desert -

One "s" because it is so dry.

dessert

- Two "s" because it is so sweet.

separate

To spell separate, just remember that it contains "a rat".

cheque - Cheque

comes in a "Q".

entrance - There is no "enter" in entrance

That is, the word "enter" is not within the word "entrance".

Other things

Least Common Factor (L.C.M) and Greatest Common Factor (G.C.F)

Thursday, October 4, 2007

Least common multiple

In arithmetic and number theory, the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. Since it is a multiple, a and b divide it without remainder. If there is no such positive integer, e.g., if a = 0 or b = 0, then lcm(a, b) is defined to be zero.

For example, the least common multiple of the numbers 4 and 6 is 12.

When adding or subtracting vulgar fractions, it is useful to find the least common multiple of the denominators, often called the lowest common denominator. For instance,

${2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},$

where the denominator 42 was used because lcm(21, 6) = 42.

Calculating the least common multiple

If a and b are not both zero, the least common multiple can be computed by using the greatest common divisor (gcd) of a and b:

$\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.$

Thus, the Euclidean algorithm for the gcd also gives us a fast algorithm for the lcm. To return to the example above, $\operatorname{lcm}(21,6) ={21\cdot6\over\operatorname{gcd}(21,6)} ={21\cdot 6\over 3}={126\over 3}=42.$

Because (ab)/c = a(b/c) = (a/c)b, one can calculate the lcm using the above formula more efficiently, by first exploiting the fact that b/c or a/c will be easier to calculate than the quotient of the product ab and c, because the fact that c is a factor of both a and b entails that in either fraction, a/c or b/c, one can completely cancel the c. This can be true whether the calculations are performed by a human, or a computer, which may have storage requirements on the variables a, b, c, where the limits may be 4-byte storage - calculating ab may cause an overflow, if storage space is not allocated properly.

Using this, we can then calculate the lcm by either using:

$\operatorname{lcm}(a,b)=\left({a\over\operatorname{gcd}(a,b)}\right)\cdot b$

$\operatorname{lcm}(a,b)=\left({b\over\operatorname{gcd}(a,b)}\right)\cdot a$

Done this way, the previous example becomes: $\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.$

Even if the numbers are large and not quickly factorable, the gcd can be calculated quickly with Euclid's algorithm.

Alternative method

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which, when combined together, make up a composite number.

For example:

$90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5. \,\!$

Here we have the composite number 90 made up of one atom of the prime number 2, two atoms of the prime number 3 and one atom of the prime number 5.

This knowledge can be used to find the lcm of a set of numbers.

Example: Find the value of lcm(45, 120, 75).

First, factor out each number and express it as a product of prime number powers.

$8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0 \,\!$

$9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0 \,\!$

$21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1. \,\!$

The lcm will be the product of multiplying the highest power in each prime factor category together. Out of the 4 prime factor categories 2, 3, 5, and 7, the highest powers from each are 2³, $\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504. \,\!$

3², 5⁰, and 7¹. Thus,

Greatest common divisor

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder.

The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The greatest common divisor is useful for reducing vulgar fractions to be in lowest terms. For example, gcd(42, 56)=14, therefore,

${42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}.$

Calculating the GCD

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18,84), we find the prime factorizations 18 = 2·3² and 84 = 2²·3·7 and notice that the "overlap" of the two expressions is 2·3; so gcd(18,84) = 6. In practice, this method is only feasible for very small numbers; computing prime factorizations in general takes far too long.

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

The series of quotients generated by the Euclidean algorithm compose a continued fraction.

If a and b are not both zero, the greatest common divisor of a and b can be computed by using least common multiple (lcm) of a and b:

$\operatorname{gcd}(a,b)=\frac{a\cdot b}{\operatorname{lcm}(a,b)}.$

Properties

Every common divisor of a and b is a divisor of gcd(a, b).

gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers. This expression is called Bézout's identity. Numbers p and q like this can be computed with the extended Euclidean algorithm.

gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. This is usually used as the base case in the Euclidean algorithm.

If a divides the product b·c, and gcd(a, b) = d, then a/d divides c.

If m is a non-negative integer, then gcd(m·a, m·b) = m·gcd(a, b).

If m is any integer, then gcd(a + m·b, b) = gcd(a, b). If m is a nonzero common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.

The gcd is a multiplicative function in the following sense: if a₁ and a₂ are relatively prime, then gcd(a₁·a₂, b) = gcd(a₁, b)·gcd(a₂, b).

The gcd is a commutative function: gcd(a, b) = gcd(b, a).

The gcd is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).

The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c), or in some different way by applying commutativity and associativity. This can be extended to any number of numbers.

gcd(a, b) is closely related to the least common multiple lcm(a, b): we have

gcd(a, b)·lcm(a, b) = a·b.

This formula is often used to compute least common multiples: one first computes the gcd with Euclid's algorithm and then divides the product of the given numbers by their gcd. The following versions of distributivity hold true:

gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).

It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below.

In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and (a, b), excluding (0, 0).

Labels: Quantitative aptitude (concepts)

posted by Unknown @ 10:05 AM

0 Comments: